<?php 
	//输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
	//解题思路
	/*利用前序遍历和中序遍历的性质来解决这个问题。 
	首先前序遍历的第一个节点是树的根节点root，在中序遍历中找到这个root，则root前面就是左子树的中序遍历结果。root后面就是右子树的中序遍历。 
	同时根据中序遍历可得到左子树的长度。 
	前序遍历中的第二个节点是左子树的根节点，以此来递归调用。
	*/
	//参考自：http://blog.csdn.net/acingdreamer/article/details/69082660
	class TreeNode{
	    var $val;
	    var $left = NULL;
	    var $right = NULL;
	    function __construct($val){
	        $this->val = $val;
	    }
	}
	//格式化输出（表格形式）
	function printTable($arr)
	{	
		echo "<table><tr>";
		for($i=0;$i<count($arr);$i++)
		{
			echo "<td>".$arr[$i]."</td>";
		}
		echo "</tr></table>";
	}

	function reConstructBinaryTree($pre, $vin)
	{ 
	    return build($pre,$vin,0,count($pre)-1,0,count($vin)-1);
	    //build(前序，后序，前序开始，前序结束，中序开始，中序结束)
	}

	function build($pre,$vin,$p_start,$p_end,$v_start,$v_end)
	{
		if($p_start > $p_end || $v_start > $v_end) return;
		$root = $pre[$p_start];

		//在中序中找到根节点，根节点前为左子树的中序遍历结果，根节点后为右子树的中序遍历结果
		for($find = $v_start;$find <= $v_end;$find++)
		{
			if($root === $vin[$find])
			{
				break;
			}
		}

		$len = $find-$v_start;//左子树长度
		$res = new TreeNode($vin[$find]);
		$res->left = build($pre,$vin,$p_start+1,$p_start+$len,$v_start,$find+1);
		$res->right = build($pre,$vin,$p_start+$len+1,$p_end,$find+1,count($vin)-1);
		return $res;
	}

	$pre = array(1,2,3,4,5,6,7);
	$vin = array(3,2,4,1,6,5,7);
	printTable($pre);
	printTable($vin);

	reConstructBinaryTree($pre, $vin);
 ?>